#include<stdio.h>
#include<stdlib.h>
/*
	栈 是限定 在表尾(栈顶)进行插入和删除操作的线性表 
	栈是一种思想  “先进后出” “后进先出”
*/

#define MAX_LEN 20		//栈的最大容量
typedef int ElemType;	//数据的类型
typedef struct SqStack
{
	ElemType * data;//data指向一块地址连续的空间，来存储栈的每一个元素
	int top;//栈顶，指定栈顶元素的下标				// top == -1   表示栈中没有元素，空栈
}sq;

//初始化一个栈
sq *InitStack()		
{
	struct SqStack * s = malloc( sizeof(struct SqStack) );
	s->data = malloc(sizeof(ElemType) * MAX_LEN);	
	s->top = -1;
						
	return s;
}
//判断是否为空栈
int IsEmpty(struct SqStack * s)
{
	//栈为空：栈不存在 || 栈里面没有元素
	if( s == NULL || s->top == -1 )
	{
		return 1;
	}
	return 0;
}

//判断栈满
int IsFull(sq *s)
{
	return (s->top==MAX_LEN-1);//从0-19
}
//入栈 1成功 0失败
int Push(sq *s,ElemType d)
{
	if(IsFull(s)||s==NULL)
	{
		printf("Push error! \n");
		return 0;	
	}
	else
	{
		s->data[++s->top]=d;
		return 1;
	}
}
//出栈
int Pop(sq *s,int *x)
{
	if(IsEmpty(s)||s==NULL)
	{
		printf("Pop error! \n");
		return 0;
	}
	else
	{
		*x=s->data[s->top--];
		return 1;
	}
}
//10进制转换N进制
void conversion(sq*s,int decimal,int N)
{
	if(decimal<0)
	{
		printf("输入的十进制数不能为负\n");
		return;
	}
	int temp,x;//中间数
	while(decimal)
	{
		temp=decimal%N;
		decimal/=N;
		Push(s, temp);
	}
	printf("result:");
	while(!IsEmpty(s))
	{
		Pop(s, &x);
		printf("%d",x);
	}
	printf("\n");
}

int main()
{
	/*
	sq *s=InitStack();
	int data,x;
	printf("请输入要入栈的元素:\n");
	while(1)
	{
		scanf("%d",&data);
		if(data==-1)
		{
			break;
		}
		Push(s, data);
	}
	printf("出栈元素:\n");
	while(!IsEmpty(s))
	{
		Pop(s, &x);
		printf("%d ",x);
	}
	*/
	sq *s=InitStack();
	int DecimalNumber,N;
	printf("请输入一个十进制数(非负)和一个要转的目的进制:\n");
	scanf("%d %d",&DecimalNumber,&N);
	conversion(s,DecimalNumber, N);

	
	return 0;
}
